//给你一个 非负 整数数组 nums 和一个整数 k 。 
//
// 如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ，那么我们称这个数组是 特别的 。 
//
// 请你返回 nums 中 最短特别非空 子数组的长度，如果特别子数组不存在，那么返回 -1 。 
//
// 
//
// 示例 1： 
//
// 
// 输入：nums = [1,2,3], k = 2 
// 
//
// 输出：1 
//
// 解释： 
//
// 子数组 [3] 的按位 OR 值为 3 ，所以我们返回 1 。 
//
// 示例 2： 
//
// 
// 输入：nums = [2,1,8], k = 10 
// 
//
// 输出：3 
//
// 解释： 
//
// 子数组 [2,1,8] 的按位 OR 值为 11 ，所以我们返回 3 。 
//
// 示例 3： 
//
// 
// 输入：nums = [1,2], k = 0 
// 
//
// 输出：1 
//
// 解释： 
//
// 子数组 [1] 的按位 OR 值为 1 ，所以我们返回 1 。 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 2 * 10⁵ 
// 0 <= nums[i] <= 109 
// 0 <= k <= 10⁹ 
// 
//
// Related Topics 位运算 数组 滑动窗口 👍 34 👎 0


package LeetCode.editor.cn;


/**
 * @author ldltd
 * @date 2025-01-17 10:35:12
 * @description 3097.或值至少为 K 的最短子数组 II
 
 */
 
public class ShortestSubarrayWithOrAtLeastKIi {
    public static void main(String[] args) {
    //测试代码
    ShortestSubarrayWithOrAtLeastKIi fun = new ShortestSubarrayWithOrAtLeastKIi();
    Solution solution= fun.new Solution();

    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        //超时
    public int minimumSubarrayLength1(int[] nums, int k) {
        int res=nums.length+1;
        for (int i = 0; i < nums.length; i++) {
            int t=0;
            for (int j = i; j < nums.length; j++) {
                t|=nums[j];
                if(t>=k) {
                    res=Math.min(j-i+1,res);
                    break;
                }
            }
        }
        return res== nums.length+1?-1:res;
    }
    //计算的粒度更低，到每一个数字的位运算，但是复杂度on
    public int minimumSubarrayLength(int[] nums, int k) {
        int n = nums.length;
        int[] bits = new int[30];
        int res = Integer.MAX_VALUE;
        for (int left = 0, right = 0; right < n; right++) {
            for (int i = 0; i < 30; i++) {
                bits[i] += (nums[right] >> i) & 1;
            }
            while (left <= right && calc(bits) >= k) {
                res = Math.min(res, right - left + 1);
                for (int i = 0; i < 30; i++) {
                    bits[i] -= (nums[left] >> i) & 1;
                }
                left++;
            }
        }

        return res == Integer.MAX_VALUE ? -1 : res;
    }

    private int calc(int[] bits) {
        int ans = 0;
        for (int i = 0; i < bits.length; i++) {
            if (bits[i] > 0) {
                ans |= 1 << i;
            }
        }
        return ans;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
